\section{Problem Description}
\label{sec:problem}

Consider the scenario where an AUV is employed to seek out hydrothermal
vents. The vehicle has been dispatched to map a region of the sea
floor. The results indicate a number of locations that merit more
detailed study. These locations can be assigned a priority based on some
estimate of the probability of finding a vent. The vehicle must
formulate a plan to visit these locations in a prudent order and make a
set of observations to detect and then document the feature of
interest. Moreover, as execution unfolds, the vehicle may spend a lot of
time at a site where a vent is found, or move on quickly after
determining no vent is present. Suppose we can estimate the costs of
traveling from each location, to each of the other locations. Then the
orienteering problem can be represented in a graph structure similar to
that outlined in Figure 2. Each node (e.g. WA, WB, WC, WD) indicates a
location of interest in the graph. The edges of the graph indicate the
cost of traversal from one location to the other. The edges can be
directed, which permits representation of different costs depending on
the direction traveled. This is especially useful where strong currents
play a role. In this example, all the goals occur at a location, though
goals could be defined along the path between locations (e.g, “take up
to 2 water samples between WA and WB”). The over-subscription planning
problem is given by:

\begin{enumerate}

\item A set of Initial Conditions (\emph{I}). This minimally includes
  the current time, the current position, and the currently available
  energy. We can treat I as a partial-plan.

\item A Goal Set (\emph{G}). Each goal has a priority. Goals are ordered
  lexicographically based on priority, 0 being the highest
  priority. Each goal has a start and end location. This allows goals to
  be specified along traverses (start != end) or at locations (start ==
  end). Finally, each goal has an estimate of cost. We assume cost is in
  terms of time and energy, and derived as a function of distance and
  speed of the vehicle.

\item A Cost Map (\emph{M}). This provides cost estimates for the edges
  in the orienteering graph.

\item A Cost Bound (\emph{B}). In our case the mission is constrained by
  finite battery capacity of the AUV and mission duration.

\end{enumerate}

The solution to the over-subscription planning problem is a
\emph{feasible plan} for a subset of goals that maximizes utility.
